package com.zx._12_算法.数据结构.tree;

import com.zx._12_算法.TreeNode;

/*
    中序、前序、后序遍历
             1
        /         \
       2           7
    /    \       /    \
    3    5       8   9
   /      \
  4        6

结果
数的值=1(2(3(4, ), 5(, 6)), 7(8, 9))
中序遍历：4,3,2,5,6,1,8,7,9,
前序遍历：1,2,3,4,5,6,7,8,9,
后序遍历：4,3,6,5,2,8,9,7,1,
 */
public class A3_各种遍历 {

    public static void main(String[] args) {
        TreeNode root = TreeNode.buildTree("1(2(3(4,),5(,6)),7(8,9))#");
        System.out.println("数的值=" + root);

        System.out.print("中序遍历：");
        inOrder(root);
        System.out.println();

        System.out.print("前序遍历：");
        preOrder(root);
        System.out.println();

        System.out.print("后序遍历：");
        postOrder(root);
        System.out.println();
    }

    /**
     * 中序遍历：左 → 根 → 右
     * 中序遍历，前序遍历，后序遍历，都可以借助递归轻松解决，递归的精髓在于甩锅
     * 中序遍历，是先遍历处理节点的左子树，然后是当前节点，对当前节点处理后，遍历处理节点的右子树
     *
     * @date: 2019年9月4日下午9:33:06
     * @author: zhangxue
     */
    public static void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.val + ",");
        inOrder(node.right);
    }

    /**
     * 后序遍历：左 → 右 → 根
     *
     * @date: 2019年9月4日下午9:33:06
     * @author: zhangxue
     */
    public static void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + ",");
        preOrder(node.left);
        preOrder(node.right);
    }

    /**
     * 后序遍历算法
     *
     * @date: 2019年9月4日下午9:33:06
     * @author: zhangxue
     */
    public static void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.val + ",");
    }
}
